package fun.ticsmyc.question;

import java.util.Arrays;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2020-02-23 11:26
 *
 * 一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右
 * 四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个
 * 矩阵中有多少个岛
 *
 * 【连通块问题】 ： 可以bfs求解  也可以用并查集
 */
public class 岛问题 {


    /**
     *  dfs
     */
    public static int countIslands(int[][] arr){
        int count =0;
        for(int i= 0 ; i<arr.length;++i){
            for(int j =0 ;j<arr[0].length;++j){
                if(arr[i][j] ==1){
                    infect(arr,i,j);
                    count++;
                }else{
                    continue;
                }
            }
        }
        return count;
    }

    private static void infect(int[][] arr,int i , int j){
        if(i<arr.length && j<arr[0].length && arr[i][j]==1){
            arr[i][j]=2;
            infect(arr,i+1,j);
            infect(arr,i-1,j);
            infect(arr,i,j+1);
            infect(arr,i,j-1);
        }else{
            return;
        }
    }

    /**
     *   连通块
     */
    public static int countIslands2(int[][] arr){
        int m = arr.length;
        int n = arr[0].length;

        int[] father = new int[m*n];
        Arrays.fill(father,-1);
        for(int i=0;i<arr.length;++i){
            for(int j=0;j<arr[0].length;++j){
                if(arr[i][j]!=0){
                    father[i*n+j] =i*n+j;
                }
            }
        }
        for(int i=0;i<arr.length;++i){
            for(int j=0;j<arr[0].length;++j){
                if(arr[i][j]!=0){
                    if(i+1<arr.length && arr[i+1][j]!=0){
                        union(father,i*n+j,(i+1)*n+j);
                    }
                    if(j+1<arr[0].length && arr[i][j+1]!=0){
                        union(father,i*n+j,i*n+j+1);
                    }
                }
            }
        }
        int ans = 0;
        for(int i=0;i<father.length;++i){
            if(father[i] ==i){
                ans++;
            }
        }
        return ans;
    }

    public static int findFather(int[] father,int a){
        if(father[a] ==a){
            return a;
        }
        father[a]=findFather(father,father[a]);
        return father[a];
    }
    public static void union(int[] father,int a,int b){
        father[findFather(father,a)] = findFather(father,b);
    }

    public static void main(String[] args) {
        int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 1, 1, 1, 0, 1, 1, 1, 0 },
                        { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                        { 0, 1, 1, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                        { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m1));
        System.out.println(countIslands2(m1));

        int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 1, 1, 1, 1, 1, 1, 1, 0 },
                        { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                        { 0, 1, 1, 0, 0, 0, 1, 1, 0 },
                        { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                        { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m2));
        System.out.println(countIslands2(m2));

    }
}
